public class Test1 {
    public static void main(String[] args) {
        int[][] arr = {{2,1,3} , {6,5,4} ,{7,8,9}};
        System.out.println(minFallingPathSum(arr));
    }
    public static int minFallingPathSum(int[][] matrix) {
        int n = matrix.length ;
        int m = matrix[0].length ;
        int[][] dp = new int[n+1][m+2];

        for(int j=0; j< n+1 ; j++){
            dp[j][0] = Integer.MAX_VALUE;
            dp[j][m+1] = Integer.MAX_VALUE;
        }

        int sum = Integer.MAX_VALUE;
        for(int i=1 ; i<= n ; i ++){
            sum = Integer.MAX_VALUE;
            for(int j=1 ; j<=m ; j ++){
                dp[i][j] = matrix[i-1][j-1] +
                        Math.min(dp[i-1][j-1] , Math.min(dp[i-1][j] ,dp[i-1][j+1]));
                sum = Math.min(sum , dp[i][j]);
            }
        }
        return sum ;
    }
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null) return 0;
        int n = obstacleGrid.length ;
        int m = obstacleGrid[0].length ;
        int[][] dp = new int[n+1][m+1];
        dp[0][1] = 1 ;
        for(int i=1 ; i <= n ; i ++){
            for(int j=1 ;j<=m ; j ++){
                if(obstacleGrid[i-1][j-1] == 1){
                    dp[i][j] = 0 ;
                }else{
                    dp[i][j] = dp[i][j-1]+dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
    public int jewelleryValue(int[][] frame) {
        if(frame == null) return 0 ;
        int n = frame.length ;
        int m = frame[0].length ;
        int[][] dp = new int[n+1][m+1] ;
        for(int i=1 ; i<= n ; i ++){
            for(int j=1 ; j <= m ; j ++){
                dp[i][j] = frame[i-1][j-1] + (dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]);
            }
        }

        return dp[n][m] ;
    }
}
